/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.backtracking;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * <p>
 * 翻译手机号码 ，按照字母序返回结果
 * Input:Digit string "23" 
 * Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
 * Although the above answer is in lexicographical order, 
 * your answer could be in any order you want. 
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com 2015年5月23日
 */
public class LetterCombinationsOfAPhoneNumber {

 public List<String> letterCombinations(String digits) {
     List<String>  result = new ArrayList<String>();
     
     //边界条件判定
     if(digits== null || digits.length() == 0){
         return result;
     }
     
     result.add("");
     //数字映射到字母  0、1、2、3、4、5、6、7、8、9
     String maps[] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
     for(int i=0;i<digits.length();i++){
         //获取映射的字符串
         String s = maps[digits.charAt(i)-'0'];
         List<String> tmp = new ArrayList<>();
         for(int j=0;j<s.length();j++){
             //把每个对应的字母加到每个结果中
             for(int k=0;k<result.size();k++){
                 //使用分期摊还的思路，保存中间结果依次附上新的元素，产生新的中间结果
                 tmp.add(result.get(k)+s.charAt(j));
             }
         }
         //保存到对应的最新结果
         result = tmp;
//         result.addAll(tmp);
     }
     
     Collections.sort(result, new Comparator<String>() {
        @Override
        public int compare(String o1, String o2) {
            return o1.compareTo(o2);
        }
     });
     return result;
    }
 
     public static void main(String[] args) {
        LetterCombinationsOfAPhoneNumber phoneNumber = new LetterCombinationsOfAPhoneNumber();
        List<String> list = phoneNumber.letterCombinations("23");
        System.out.println(list);
        list = phoneNumber.letterCombinations("9");
        System.out.println(list);
    }
}
